package leetcode.code1005;

import java.util.Arrays;

public class Solution extends S1005 {

	@Override
	public int largestSumAfterKNegations(int[] nums, int k) {
		Arrays.sort(nums);
		int LEN = nums.length;
		int ans = 0;
		int i = 0;
		int num = 0;
		int last = 0;
		while (k > 0) {
			if (i < LEN && (num = nums[i]) < 0) {
				num = -num;
				last = num;
				ans += num;
				k--;
				i++;
			} else {
				if (num > 0 && k > 0 && (k & 1) == 1) {
					if (i == 0 || num < last) {
						ans -= num;
						i++;
					} else {
						ans -= last << 1;
					}
				}
				break;
			}
		}
		while (i < LEN) {
			ans += nums[i];
			i++;
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution solution = new Solution();
		solution.debug6();
		solution.debug5();
		solution.debug1();
		solution.debug2();
		solution.debug3();
		solution.debug4();

	}

}
